/**
 * 
 */
package cn.edu.nju.ws.sview.wyge.relations.adataset.relations;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author Weiyi Ge (geweiyi@gmail.com) 2012-8-15
 * 
 */
public class UnionFind {
	// The trees of Nodes that represent the disjoint sets.
	HashMap<String, Node> nodes;

	public static void main(String[] argus) {
		UnionFind uf = new UnionFind();
		uf.union("a", "c");
		uf.union("c", "d");
		uf.union("e", "f");
		System.out.println(uf.find("a"));
		System.out.println(uf.find("b"));
		System.out.println(uf.find("c"));
		System.out.println(uf.find("d"));
		System.out.println(uf.find("e"));
		System.out.println(uf.find("f"));
	}

	/**
	 * Constructor.
	 */
	public UnionFind() {
		nodes = new HashMap<String, Node>();
	}

	/**
	 * Constructor. Make a <tt>UnionFind</tt> with a given number of disjoint
	 * sets.
	 */
	public UnionFind(int size) {
		nodes = new HashMap<String, Node>(size);
	}

	/**
	 * Searches the disjoint sets for a given integer. Returns the set
	 * containing the integer a. Sets are represented by a local class
	 * <tt>Node</tt>.
	 */
	public Node findNode(String a) {

		Node na = (Node) nodes.get(a);

		if (na == null) {
			// Start a new set with a
			Node root = new Node(a);

			nodes.put(a, root);

			return root;
		}

		return findNode(na);
	}

	/**
	 * Returns the integer value associated with the first <tt>Node</tt> in a
	 * set.
	 */
	public String find(String a) {
		return findNode(a).value;
	}

	/**
	 * Finds the set containing a given Node.
	 */
	private Node findNode(Node node) {
		Stack<Node> stack = new Stack<Node>();

		// Find the root element.
		while (node.parent != null) {
			stack.push(node);
			node = node.parent;
		}

		// Do path compression on the way back down.
		Node root = node;

		while (!stack.empty()) {
			node = (Node) stack.pop();
			node.parent = root;
		}

		return root;
	}

	/**
	 * Returns true if a and b are in the same set.
	 */
	public boolean isEquiv(String a, String b) {
		return findNode(a) == findNode(b);
	}

	/**
	 * Combines the set that contains a with the set that contains b.
	 */
	public void union(String a, String b) {
		Node na = findNode(a);
		Node nb = findNode(b);

		if (na == nb) {
			return;
		}

		// Link the smaller tree under the larger.
		if (na.rank > nb.rank) {
			// Delete nb.
			nb.parent = na;
			na.value = b;
		} else {
			// Delete na.
			na.parent = nb;
			nb.value = b;
			if (na.rank == nb.rank) {
				nb.rank++;
			}
		}
	}

	class Node {
		Node parent; // The root of the tree in which this Node resides
		String value;
		int rank; // This Node's height in the tree

		public Node(String v) {
			value = v;
			rank = 0;
		}
	}

}
